package slidingWindow;

import org.junit.Test;

import java.util.HashMap;

/*
 *@description 最小覆盖子串
 *@author hkfan
 *@version 1.0
 *@create 2025/6/3 16:23
 */
public class LeetCode_76 {

    @Test
    public void test(){
        System.out.println(minWindow("ADOBECODEBANC","ABC"));
    }


    public String minWindow(String s, String t) {
        if (s.length()<t.length()){
            return "";
        }
        //1. 定义
        int l=0,r=0,size=0;//size记录map中大于0的个数
        String res = "";
        HashMap<Character,Integer> map = new HashMap<>();
        //2. 录入map中
        for (int i = 0; i < t.length(); i++) {
            map.put(t.charAt(i),map.getOrDefault(t.charAt(i),0)+1);
        }
        size=map.keySet().size();
        //3. 循环
        for (; r < s.length(); r++) {
            char temp = s.charAt(r);
            if (map.containsKey(temp)){
                map.put(s.charAt(r),map.get(s.charAt(r))-1);
                if (map.get(s.charAt(r))==0){
                    size--;
                }
                if (size==0){
                    while (true){
                        char temp1 = s.charAt(l);
                        if (map.containsKey(temp1)){
                            if (map.get(s.charAt(l))<0){
                                map.put(s.charAt(l),map.get(s.charAt(l))+1);
                                l++;
                            }else {
                                break;
                            }
                        }else {
                            l++;
                        }
                    }
                    map.put(s.charAt(l),map.get(s.charAt(l))+1);
                    size++;
                    if (res.equals("")|| r - l + 1 < res.length()){
                        res = s.substring(l,r+1);
                    }
                    l++;
                }
            }
        }
        return res;
    }



}
